<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>希尔排序</title>
  </head>
  <body>
    <script>
      /*
       * 希尔排序（Shell Sort）思路：
       * 按一定步长step=length/2对数组进行分组，对每组用直接插入排序方法进行排序。
       * 随着step = step/2 的方式缩小，所分成的组越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
       */
      var shellArr = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0];
      console.log("希尔排序=", shellSort(shellArr));

      //希尔排序函数
      function shellSort(array) {
        //计算步长值
        var length = array.length;
        //遍历所有步长
        for (
          let step = Math.floor(length / 2);
          step > 0;
          step = Math.floor(step / 2)
        ) {
          //遍历所有元素
          for (let i = step; i < array.length; i++) {
            //遍历本组中所有元素
            for (let j = i - step; j >= 0; j -= step) {
              //如果当前元素大于机上步长后的那个元素，则交换位置
              if (array[j] > array[j + step]) {
                var temp = array[j];
                array[j] = array[j + step];
                array[j + step] = temp;
              }
            }
          }
        }
        return array;
      }
    </script>
  </body>
</html>
